package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2328. 网格图中递增路径的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/31 17:29
 */
public class CountPaths {

    public static void main(String[] args) {
        CountPaths test = new CountPaths();

        // 8
//        int[][] arr = {{1, 1}, {3, 4}};

        //
        int[][] arr = Utils.getArr(100, 500, 1, 100000);

        int i = test.countPaths(arr);
        System.out.println(i);
    }

    private int[][] grid;
    private int m;
    private int n;
    private int[][] arr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int countPaths(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        int[][] counts = new int[m][n];
        PriorityQueue<Long> queue = new PriorityQueue<>();
        for (int i = 0; i < m; i++) {
            int[] items = grid[i];
            for (int j = 0; j < n; j++) {
                long t = items[j];
                queue.add((t << 32) + (i << 12) + j);
            }
        }
        long sum = 0;
        int length = m * n;
        while (length > 0) {
            length--;
            Long v = queue.poll();
            find(counts, v.intValue() >> 12, (int) (v & 0XFFF));
        }
        for (int i = 0; i < m; i++) {
            int[] items = counts[i];
            for (int t : items) {
                sum += t;
            }
        }
        return (int) (sum % 1000000007);
    }

    private void find(int[][] counts, int x, int y) {
        long s = 1;
        int v = grid[x][y];
        for (int[] ints : arr) {
            int i = x + ints[0];
            int j = y + ints[1];
            if (i < 0 || j < 0 || i == m || j == n) {
                continue;
            }
            if (grid[i][j] >= v) {
                continue;
            }
            s += counts[i][j];
        }
        counts[x][y] = (int) (s % 1000000007);
    }

}
